package StruttureDati;

public class Copertura {
	static int[] insieme;
	static SimpList<int[]> famigliaSottoinsiemi;
	static SimpList<int[]> listaSoluzione=null;
	static boolean nonTrovato=true;
	
	//metodo che presa una matrice di incidenza stampa su schermo, se trovata, la lista di sottoinsiemi che ricoprono l'insieme
	public static void soluzione(int[][] matrice){
		int i = 0;
		while(nonTrovato){
			if(matrice==null){
				System.out.println(listaSoluzione.toString());
				nonTrovato=false;
				}
			else{
				while(numeroUnoRiga(matrice[i])!=0 && i<matrice[i].length){
					if(numeroUnoRiga(matrice[i])!=0){
						listaSoluzione=new SimpList<int[]>(matrice[i],listaSoluzione);
						}
					else i++;
					}
				int[][] nuovaMatrice = nuovaMatrice(matrice, i);
				soluzione(nuovaMatrice);
				}
			i++;
			}
		}
	
	//metodo per creare la matrice su cui applicare l'algoritmo risolutivo
	public static int[][] creaMatrice(int[] insieme, SimpList<int[]> famiglia){
		int[][] matrice = new int[insieme.length][numeroElementi(famiglia)];
		for(int i=0; i<matrice.length; i++){
			for(int j=0; j<matrice[i].length; j++){
				matrice[i][j]=0;
			}
		}

		int i=0;
		for(int[] appoggio=famiglia.head(); appoggio!=null; famiglia=famiglia.tail()){
			for(int j=0; j<insieme.length; j++){
				if(appoggio[i]==insieme[j])
					matrice[i][j]=1;
			}
			i++;
		}
		return matrice;
		}
	
	//metodo per calcolare il numero degli elementi in una lista
	public static int numeroElementi(SimpList<int[]> lista){
		int count=0;
		while(lista!=SimpList.EMPTYLIST){
			count++;
			lista=lista.tail();
		}
		return count;
	}
	
	//metodo per creare la nuova matrice su cui fare la ricorsione
	public static int[][] nuovaMatrice(int[][] matrice, int i){
		int[][] nuovaMatrice = new int[matrice.length-i][matrice[0].length-numeroUnoRiga(matrice[0])];
		for(int k=0; i<matrice.length; i++){
			if(matrice[i][k]==0){
			for(int j=0; j<matrice[i].length;j++){
					nuovaMatrice[i][j] = matrice[i][j];}
				}
			k++;
		}
			
		return nuovaMatrice;
	}
	
	//metodo per calcolare il numero di 1 presenti in una riga
	public static int numeroUnoRiga(int[] riga){ 
		int i = 0;
		int count=0;
		while(i<riga.length){
			if(riga[i]==1) count++;
			i++;
		}
		return count;
	}
		
	public static void main(String[] args){}
}